//字符串相乘
class Solution {
public:
    string _multiply(const string& str , char ch)
    {

        int next = 0;
        string ret;
        for(int i = str.size() - 1 ; i >= 0 ; --i)
        {
            int t = (str[i]-'0') * (ch -'0') + next;
            next = t / 10;
            ret += to_string (t % 10);
        }

        if(next) ret += to_string(next);
        return ret;
    }
    string StrAddStr(const string& s1 ,const string& s2)
    {
        int maxlen = max(s1.size() , s2.size());
        int next = 0;
        string ret;
        for(size_t i = 0 ; i < maxlen ; ++i)
        {
            int temp1 = 0 , temp2 = 0;
            if(i < s1.size()) temp1 = s1[i]-'0';
            if(i < s2.size()) temp2 = s2[i]-'0';

            int t = temp1 + temp2 + next;
            next = t/10;
            ret += to_string(t%10);
        }
        if(next) ret+= to_string(next);
        return ret;
    }
    string multiply(string nums1, string nums2) {
        //把nums1与nums2的每一位相乘，最后加起来就是答案
        string sum = "0";
        int n = nums2.size();
        for(size_t i = 0 ; i < n ; ++i)
        {
            string temp;
            for(int j = n-i-2 ; j >= 0 ; --j)
            {
                temp += '0';
            }
            temp += _multiply(nums1,nums2[i]);
            sum = StrAddStr(temp,sum);
        }
        reverse(sum.begin() , sum.end());
        if(sum[0] == '0') return "0";
        return sum;
    }
};

//二进制求和
class Solution {
public:
    string addBinary(string a, string b) {
      reverse(a.begin(),a.end());
      reverse(b.begin(),b.end());
      int maxlen = max(a.size(),b.size());
      int next = 0;
      string ret;
      for(size_t i = 0 ; i < maxlen ; ++i)
      {
          int aVal = 0 , bVal = 0;
          if(i < a.size()) aVal = a[i]-'0';
          if(i < b.size()) bVal = b[i]-'0';
          int t = aVal + bVal + next;
          next = t/2;
          ret += to_string(t%2);
      }
      if(next) ret += to_string(next);
      reverse(ret.begin() , ret.end());
      return string(ret.begin() , ret.end());
    }
};

//最长回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int ret_start = 0;
        int ret_end = 0;
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j])
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;

                if(dp[i][j] == true && ret_end - ret_start < j-i)
                {
                    ret_start = i;
                    ret_end = j;
                }
            }
        }
        std::cout << ret_start << " " << ret_end << std::endl;
        string ret(s.begin()+ret_start,s.begin()+ret_end+1);
        return ret;
    }
};

//最长公共前缀
class Solution {
public:
string bothlongestComPre(string s1,string s2)
{
   //找到两者的最长公共前缀
   int minlen = min(s1.size() , s2.size());
   string prefix;
   for(int i = 0 ; i < minlen ; ++i)
   {
       if(s1[i] != s2[i]) break;
       prefix += s1[i]; 
   }
   return prefix;
}
    string longestCommonPrefix(vector<string>& strs) {
      if(strs.size() == 1) return strs[0];
      else if(strs.size() == 0) return "";
      string prefix = bothlongestComPre(strs[0] , strs[1]);
      for(size_t i = 2 ; i < strs.size() ; ++i)
      {
          prefix = bothlongestComPre(prefix,strs[i]);
          if(prefix == "") break;
      }
      return prefix;
    }
};